Robust filtered predicates ( CGAL_Filtered_exact<CT,ET>)

The class CGAL_Filtered_exact<CT,ET> is a wrapper type for the number type CT, with the difference that all predicates are specialized such that they are guaranteed to be exact. Speed is achieved via a filtering scheme using interval arithmetic (see Section ). Here are the necessary requirements:

• CT is the construction and storage type. The only data member of the class CGAL_Filtered_exact<CT,ET> is the value of type CT. All arithmetic operations called outside the predicates will be executed with this number type. You can disable this feature by compiling with the flag -DCGAL_DENY_INEXACT_OPERATIONS_ON_FILTER (it allows the programmer to spot the inexact operations that should be incorporated in the predicates). The arithmetic operations called from the predicates are always computed exactly.
• The ET type must be able to compute exactly the operations involved in the predicates called.
• A CGAL_convert_to<CGAL_Interval_nt_advanced>(CT) function must be provided, that returns an interval containing the value of the argument of type CT. This conversion function has to be as fast as possible, and exact (in the sense that the interval must contain surely the initial value). This function is provided for the usual types CGAL_Gmpz, leda_real, leda_rational, leda_bigfloat, leda_integer, and the built-in types. The user can add his own types.

• A CGAL_convert_to<ET>(CT) function must also be provided, that returns a number of type ET representing exactly the argument of type CT. It's a conversion function that is used for the exact computation, when the filter fails. This conversion has to be done exactly.

Example

    #include<CGAL/Arithmetic_filter.h>
    #include<CGAL/leda_real.h>
    #include<CGAL/double.h>
    typedef CGAL_Filtered_exact<double, leda_real> NT;

Or if you are sure that the predicates involved do not use divisions nor square roots:

    #include<CGAL/Arithmetic_filter.h>
    #include<CGAL/Gmpz.h>
    #include<CGAL/int.h>
    typedef CGAL_Filtered_exact<int, CGAL_Gmpz> NT;

And if you know that the double variables contain integer values, you can use:

    #include<CGAL/Arithmetic_filter.h>
    #include<CGAL/Gmpz.h>
    #include<CGAL/double.h>
    typedef CGAL_Filtered_exact<double, CGAL_Gmpz> NT;

Implementation

For each predicate file, the overloaded code is generated automatically by a PERL script ( examples/Interval_arithmetic/filtered_predicate_converter) that you can use for your own predicates (see examples/Interval_arithmetic/README). This script parses the template declaration of the functions and generates the overloaded code the following way:

• convert the entries to intervals using CGAL_convert_to<CGAL_Interval_nt_advanced>(CT),
• call the original template function with the type CGAL_Interval_nt_advanced,
• if no exception is thrown, return the value,
• if an exception is thrown (the filter failed), convert the original entries using CGAL_convert_to<ET>(CT),
• and call the original template function with the type ET.

Example